package org.example.graph_theory;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Redundant_connection_II {
    public static void main(String[] args) {
        //冗余连接 II

        //在本问题中，有根树指满足以下条件的 有向 图。该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。
        //输入一个有向图，该图由一个有着 n 个节点（节点值不重复，从 1 到 n）的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间，这条附加的边不属于树中已存在的边。
        //结果图是一个以边组成的二维数组 edges 。 每个元素是一对 [ui, vi]，用以表示 有向 图中连接顶点 ui 和顶点 vi 的边，其中 ui 是 vi 的一个父节点。
        //返回一条能删除的边，使得剩下的图是有 n 个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。

        int[][] edges = {{1,2},{1,3},{2,3}};
//        int[][] edges = {{1,2},{2,3},{3,4},{4,1},{1,5}};
//        int[][] edges = {{2,1},{3,1},{4,2},{1,4}};
        int[] redundantDirectedConnection = findRedundantDirectedConnection(edges);
        System.out.println(Arrays.toString(redundantDirectedConnection));
    }




    //并查集理论
    public static int[] findRedundantDirectedConnection(int[][] edges) {
        int[] father = new int[edges.length+1]; //父节点
        int[] ancestor = new int[edges.length+1]; //根节点

        for (int i = 1; i < father.length; i++) {
            father[i] = i;
            ancestor[i] = i;
        }

        int conflict = -1;
        int circle = -1;

        for (int i = 0; i < edges.length; i++) {
            int s = edges[i][0];
            int d = edges[i][1];
            if (father[d] != d){
                conflict = i;
            }else {

                father[d] = s;

                int roots = find(s, ancestor);
                int rootd = find(d, ancestor);

                if (roots == rootd) {
                    circle = i;
                }else {
                    //连接
                    ancestor[rootd] = roots;
                }
            }
        }

        if (conflict < 0 ) return edges[circle];
        if (circle < 0 ) return edges[conflict];
        return new int[]{father[edges[conflict][1]],edges[conflict][1]};

    }

    public static int find(int node,int[] ancestor){
        if (ancestor[node] != node){
            ancestor[node] = find(ancestor[node],ancestor); //压缩路径
        }
        return ancestor[node];
    }


}
